package com.wu.convert;

import java.util.ArrayList;

/**
 * 二叉搜索树与双向链表
 */
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}

public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        ArrayList<Integer> list = new ArrayList<>();
        ArrayList<Integer> treeNodes = inOrder(pRootOfTree, list);
        TreeNode treeNode = new TreeNode(list.get(0));
        TreeNode tem = treeNode;
        for (int i = 1; i < treeNodes.size(); i++) {
            if (treeNodes.get(i) != -1) {
                tem.right = new TreeNode(treeNodes.get(i));
                tem.right.left = tem;
            }
            tem = tem.right;
        }
        return treeNode;
    }

    private ArrayList<Integer> inOrder(TreeNode pRootOfTree, ArrayList<Integer> list) {
        if (pRootOfTree == null) {
            return null;
        }
        if (pRootOfTree.left != null) {
            inOrder(pRootOfTree.left, list);
        }
        list.add(pRootOfTree.val);
        if (pRootOfTree.right != null) {
            inOrder(pRootOfTree.right, list);
        }
        return list;
    }
}